package baseclass.g_prefixtree;

/**
 * @date 2020/2/29 20:31
 */
class PreNode {
    int path;//多少个单词 路过该节点
    int end;//有多少个单词以当前节点结尾
    //可以这样存储，字符是key，value存放着path,end以及trieNode信息。
    // 泛型一改，可以存任何东西
    //HashMap<Character,TrieNode> trieNode;
    PreNode[] nexts; //存储着26个字母的线路
    Character ele;
    public PreNode() {
        this.path = 0;
        this.end = 0;
        this.nexts = new PreNode[26];
    }
}

public class PrefixTree {

    private PreNode root;

    public PrefixTree() {
        //根节点，path=end=0，维护着26条路
        this.root = new PreNode();
    }

    public void insert(String word) {
        if (word == null || word.length() == 0) return;
        //从上到下依次遍历
        PreNode node = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            int nextIndex = c - 'a';
            //注意这里不能先 node = node.nexts[nextIndex];
            //因为如果此时node为0，new PreNode后 node和上面的PreNode连不到一块了
            //没有插入过,创建新节点
            if (node.nexts[nextIndex] == null) {
                node.nexts[nextIndex] = new PreNode();
            }
            node = node.nexts[nextIndex];
            node.ele = c;
            //否则path++
            node.path++;
        }
        node.end++;
    }

    /**
     * 查找某个单词出现了几次
     */
    public int search(String word) {
        if (word == null || word.length() == 0) return 0;
        //从上到下依次遍历
        PreNode node = root;
        for (int i = 0; i < word.length(); i++) {
            int nextIndex = word.charAt(i) - 'a';
            if (node.nexts[nextIndex] == null) return 0;
            node = node.nexts[nextIndex];
        }
        return node.end;
    }
    public boolean doSearch(String word) {
        return search(word) >= 1;
    }

    public boolean startsWith(String prefix) {
        if (prefix == null || prefix.length() == 0) return false;
        //从上到下依次遍历
        PreNode node = root;
        for (int i = 0; i < prefix.length(); i++) {
            int nextIndex = prefix.charAt(i) - 'a';
            if (node.nexts[nextIndex] == null) return false;
            node = node.nexts[nextIndex];
        }
        return true;
    }

    public boolean contains(String word) {
        return search(word) != 0;
    }

    public void delete(String word) {
        if (word == null || word.length() == 0) return;
        //从上到下依次遍历
        PreNode node = root;
        for (int i = 0; i < word.length(); i++) {
            int nextIndex = word.charAt(i) - 'a';

            //根本不存在该单词
            if (node.nexts[nextIndex] == null) return;
            //否则path--,如果path为0，可以提前删除下面所有节点，
            // 因为必定是当前word的所属节点
            if (--node.nexts[nextIndex].path == 0) {
                node.nexts[nextIndex]  = null;
                return;
            }
            node = node.nexts[nextIndex];
        }
        node.end--;
    }

    /**
     * 以word为前缀的单词出现的次数。
     * 和搜索整个单词出现次数一样逻辑，
     * 最后返回值一个是node.path一个是node.end
     */
    public int prefixNumber(String word) {
        if (word == null || word.length() == 0) return 0;
        //从上到下依次遍历
        PreNode node = root;
        for (int i = 0; i < word.length(); i++) {
            int nextIndex = word.charAt(i) - 'a';
            node = node.nexts[nextIndex];
            if (node == null) return 0;
        }
        return node.path;
    }

    public static void main(String[] args) {
        PrefixTree trie = new PrefixTree();
        trie.insert("apple");
        System.out.println(trie.doSearch("apple"));
        System.out.println(trie.doSearch("app"));
        System.out.println(trie.startsWith("app"));
        trie.insert("app");
        System.out.println(trie.doSearch("app"));


        /*System.out.println(trie.search("zuo"));
        trie.insert("zuo");
        System.out.println(trie.search("zuo"));
        trie.delete("zuo");
        System.out.println(trie.search("zuo"));
        trie.insert("zuo");
        trie.insert("zuo");
        trie.delete("zuo");
        System.out.println(trie.search("zuo"));
        trie.delete("zuo");
        System.out.println(trie.search("zuo"));
        trie.insert("zuoa");
        trie.insert("zuoac");
        trie.insert("zuoab");
        trie.insert("zuoad");
        trie.delete("zuoa");
        System.out.println(trie.search("zuoa"));
        System.out.println(trie.prefixNumber("zuo"));*/
    }

}
